%\documentclass[times, 10pt,twocolumn]{sigplanconf}
\documentclass[letterpaper,twocolumn,10pt]{article}
\usepackage{usenix,epsfig,endnotes}
\usepackage[numbers]{natbib}

\usepackage{times}

\usepackage{graphicx}
%\usepackage{balance}  % for  \balance command ON LAST PAGE  (only there!)
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{calc}
\usepackage{subfigure}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{listings} 
\usepackage[T1]{fontenc}
\usepackage[ansinew]{inputenc}

\usepackage[draft]{fixme}
\usepackage{soul}
\fxsetup{
    status=draft,
    author=,
    layout=inline,
    theme=color
}
            
\lstset{language=Java,
basicstyle=\ttfamily\small
}


\definecolor{fxnote}{rgb}{0.8000,0.0000,0.0000}
% define the background colour:
\colorlet{fxnotebg}{yellow}

% refedine the layout macro:
\makeatletter
\renewcommand*\FXLayoutInline[3]{%
  \@fxdocolon {#3}{%
    \@fxuseface {inline}%
    \begingroup
      \sethlcolor{fx#1bg}%
      \color {fx#1}\ignorespaces \hl{#3\@fxcolon #2}%
    \endgroup}}
\makeatother



\setcounter{tocdepth}{3}

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}

\newcommand{\name}{LOOM}
\newcommand{\fullname}{Lightweight Optimal Overlay Mechanism}

\begin{document}

\special{papersize=8.5in,11in}
\setlength{\pdfpageheight}{\paperheight}
\setlength{\pdfpagewidth}{\paperwidth}
\setlength{\bibsep}{0.5pt}
\renewcommand{\arraystretch}{1.5}

\title{\name: Optimal Aggregation Overlays for In-Memory BigData
Processing\thanks{Financially supported by DARPA grant \# N11AP20014, Purdue Research Foundation grant \# 205434, and Google Award ``Geo-Distributed Big Data Processing''.}}

\author{
{\rm William Culhane}\
Purdue University
\and
{\rm Kirill Kogan}\
Purdue University
\and
{\rm Chamikara Jayalath}\
Purdue University
\and
{\rm Patrick Eugster}\
Purdue University
% copy the following lines to add more authors
% \and
% {\rm Name}\\
%Name Institution
} % end author
%William Culhane~~~~Chamikara Jayalath~~~~Patrick Eugster~~~~
%Kirill Kogan\\Purdue University\\ \{wculhane,cjayalat,peugster,kkogan\}@purdue.edu}
\date{}

\maketitle

\begin{abstract}
Aggregation underlies the distillation of information from big data. Many
well-known basic operations including top-$k$ matching and word count 
hinge on fast aggregation across large data-sets. Common frameworks including
MapReduce support aggregation, but do not explicitly consider or optimize it.
Optimizing aggregation however becomes yet more relevant in recent ``online'' approaches to
expressive big data analysis which store data in main memory across nodes. This
shifts the bottlenecks from disk I/O to distributed computation and network
communication and significantly increases the impact of aggregation time on
total job completion time.

This paper presents \name, a (sub)system for efficient big data aggregation for use 
within big data analysis frameworks. \name\ efficiently
supports two-phased (sub)computations consisting in a first phase
performed on individual data sub-sets (e.g., word count, top-$k$
matching) followed by a second aggregation phase which consolidates individual
results of the first phase (e.g., count sum, top-$k$). Using characteristics of
an aggregation function, \name\ constructs a specifically configured
aggregation overlay to minimize aggregation costs. 
 We present and prove optimal heuristics and experimentally demonstrate the
 benefits of thus optimizing aggregation overlays using microbenchmarks and real world examples.
\end{abstract}

\input{intro}
\input{related}
\input{model}
%\input{proofs}
\input{newmath}
\input{system}
\input{experiments}
\input{conclusions}

{\footnotesize \bibliographystyle{acm}
\bibliography{references}}

\end{document}
